This disclosure relates to data storage, for example (though not exclusively) in the context of cache memories.
Fully associative cache memories are typically implemented with a so-called tag array which holds tags, the tags being examples of identifiers associated with lines or partitions of the cache memory which are indicative of the data stored in those partitions. A bank of comparators, one for each cache line or partition, compares the stored tags with information derived from a request for access to the cache memory. A data array holds actual cache lines (the data).
In order to be able to read all the stored tags in every clock cycle that has a valid request, the tags are typically held in flip-flops to allow simultaneous comparisons of the tag corresponding to a current request with multiple sets of tags. In a fully associative arrangement, all tag bits for all tags have to be compared, so the number of flip-flops increases with the tag size. Possible disadvantages of this type of fully associative caches include the on-chip flip-flop area required for tag storage, the power of doing full tag comparisons every active clock cycle (for example, when accesses do not exhibit good spatial locality) and the timing of the comparison logic that is likely to be in a critical path.
On the other hand, set-associative caches, where any particular data item is restricted to a set (that is to say, a subset) of available locations, allow the tag array to be stored in memory such as SRAM (static random access memory) where a limited number of tags are read out in any one clock cycle, and only need a limited number of comparators. They are therefore likely to be more power and area efficient at each access or lookup, but they are limited by their cache placement policy and cannot necessarily be used for applications that really require a fully associative cache. These would be applications where an ability to store a data item to any available location of a cache regardless of the value of the tags is mandatory (the set-associative organization might be a problem for special-purpose caches where tags are not addresses) or certain associative buffers where there might be a requirement to hold a number of recent items and a need to perform random lookups.
It is a constant aim to improve the efficiency and/or flexibility of data storage.